package com.sortingalgorithm;

import java.util.Arrays;
import java.util.Scanner;

public class MaxHeapSort2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] arr = new int[N];
        for(int i = 0;i < N;i++){
            arr[i] = sc.nextInt();
        }
        // 构建初试堆
        buildInitMaxHeap(arr,N);
        int t = N;
        for(int i = t - 1;i > 0;i--){
            swap(arr,0,i);
            N--;
            adjustHeap(arr,0,N);
        }
        System.out.println(Arrays.toString(arr));

    }

    private static void buildInitMaxHeap(int[] arr,int len){
        for (int i = (int) Math.floor(len >> 1) - 1;i >= 0;i--){
            adjustHeap(arr,i,len);
        }
    }

    private static void adjustHeap(int[] arr,int i,int len){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIndex = i;
        if(left < len && arr[left] > arr[maxIndex]){
            maxIndex = left;
        }
        if(right < len && arr[right] > arr[maxIndex]){
            maxIndex = right;
        }
        if(i != maxIndex){
            swap(arr,i,maxIndex);
            adjustHeap(arr,maxIndex,len);
        }
    }

    private static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
